#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


class Solution:
    def reorderList(self, head):
        if not (head and head.next):
            # 只有1个和两个节点, 直接返回
            return head

        front_head = head
        mid = self.find_mid(head)

        behind_head = self.reverse(mid.next)
        mid.next = None     # disconnect mid and behind

        return self.alternately_merge(front_head, behind_head)

    def find_mid(self, head):
        # 奇书: 找出真正中点
        # 偶数: 找出偏左
        # 统统取mid.next 作为right后半部分
        slow = fast = head

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        return slow

    def reverse(self, head):
        # 循环遍历: 把指针方向扭转
        # 1 ---> 2 ----> 3
        # 1 <--- 2 <---- 3
        pre, cur = None, head

        while cur:
            # save
            next = cur.next

            # update: pivot
            cur.next = pre

            # drive loop
            pre, cur = cur, next

        return pre

    def alternately_merge(self, front_head, behind_head):
        # 交叉合并
        front_cur  = front_head
        behind_cur = behind_head

        # front的个数大余等于behind(是有find_mid那里处理的)
        while behind_cur:
            assert front_cur

            front_next_save = front_cur.next
            behind_next_save = behind_cur.next

            # link and drive
            front_cur.next = behind_cur
            behind_cur.next = front_next_save

            # drive
            front_cur  = front_next_save
            behind_cur = behind_next_save

        return front_head


def show(n):
    while n:
        print("%s ----> " % n.val, sep=' ', end=' ')
        n = n.next
    print()


def main():
    print("start main")

    # v5 = ListNode(5)
    v4 = ListNode(4, None)
    v3 = ListNode(3, v4)
    v2 = ListNode(2, v3)
    v1 = ListNode(1, v2)
    v0 = ListNode(0, v1)

    s = Solution()
    ret = s.reorderList(v2)
    show(ret)

    # ret = s.find_mid(v0)
    # print(ret.val)

    # ret = s.reverse(ret.next)
    # print(ret.val)
    # print(ret.next.val)
    # print(ret.next.next)

    # s.alternately_merge(v0, )

if __name__ == "__main__":
    main()
